package 华为OD机试真题2023.基础题;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class HJ48_MVP争夺战 {
    static int TARGET, TOTAL;

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/基础题/input/48.txt"));
        int N = in.nextInt();
        in.nextLine(); //吸收回车
        int[] score = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(score);
        TOTAL = Arrays.stream(score).sum();
        int maxn = TOTAL / 2;
        int minn = Arrays.stream(score).max().getAsInt();
        for (int i = minn; i <= maxn; i++) {
            if (TOTAL % i == 0) {
                TARGET = i;
                dfs(TOTAL / i, N - 1, TARGET, score);
            }
        }
    }

    static void dfs(int person, int startIndex, int target, int[] score) {
        if (person == 0) {
            System.out.println(TARGET);
            System.exit(0);
        }
        if (target == 0) {
            dfs(person - 1, score.length - 1, TARGET, score);
        }
        if (startIndex < 0) { //此时第 1 个也加入了计算，得先判断结果是否合理再退出
            return;
        }
        for (int i = startIndex; i >= 0; i--) {
            if (score[i] == 0) {
                continue;
            }
            int tmp = score[i];
            if (tmp <= target) {
                score[i] = 0;
                dfs(person, i - 1, target - tmp, score);
                score[i] = tmp;
            }
//            dfs(person, i - 1, target, score); //必须从大到小连着找下去，不能跳着找
        }
    }
}
